package Maze;

public class Maze1 {
    //出口目标点坐标
    private static final int X = 9;
    private static final int Y = 8;
    //定义(9,8)为出口
    private static final int MaxSize = 200;
    //迷宫路径
    int[][] maze = {
            {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
            {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
            {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
            {1, 0, 0, 0, 0, 1, 1, 0, 1, 1},
            {1, 0, 1, 1, 1, 0, 0, 1, 0, 1},
            {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
            {1, 0, 1, 0, 0, 0, 1, 0, 1, 1},
            {1, 0, 1, 1, 1, 1, 0, 0, 1, 1},
            {1, 1, 1, 0, 0, 0, 1, 0, 1, 1},
            {1, 1, 1, 0, 0, 0, 0, 0, 0, 1},
            {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
    };

    Node Stack[] = new Node[MaxSize];

    //栈顶指针
    int top = -1;
    //路径的计数
    int count = 1;

    public Maze1() {
        System.out.println("路径如下：");
        mazePath(1,1,X,Y);
    }
    //寻路方法
    public void mazePath(int xi,int yi,int xe,int ye){
        int i,j,d,flag;
//初始化栈 起始地点入栈
        top++;
        Node n = new Node();
        Stack[top] = n;
        System.out.println(Stack[top]);
        Stack[top].i = xi;
        Stack[top].j = yi;
        Stack[top].d = -1;
        maze[xi][yi] = -1;
//如果栈不为空就继续探路
        while(top>-1){
//取出栈顶元素
            i = Stack[top].i;
            j = Stack[top].j;
            d = Stack[top].d;
//判断是否已经找到目标点出口  如果找到出口那么打印路径
            if(i==xe && j ==ye){
                System.out.println("第"+(count++)+"路径");
                for(int k = 0;k <= top;k++){
                    System.out.printf("("+Stack[k].i+","+Stack[k].j+","+Stack[k].d+")->");
//每行打印5个坐标点后换行
                    if((k+1)%5==0){
                        System.out.println("");
                    }
                }
                System.out.println("");

                maze[Stack[top].i][Stack[top].j] = 0;
                top--;
                i = Stack[top].i;
                j = Stack[top].j;
                d = Stack[top].d;
            }
//根据四个方向试探性的查找可行路径
            flag = 0;//用来标记是否已经找到可行路径  0 没找到  1找到
            while(flag==0 && d<4){
                d++;
                switch(d){
                    case 0: i = Stack[top].i-1;j= Stack[top].j;break;//上
                    case 1: i = Stack[top].i+1;j= Stack[top].j;break;//下
                    case 2: i = Stack[top].i;j= Stack[top].j-1;break;//左
                    case 3: i = Stack[top].i;j= Stack[top].j+1;break;//右
                }
                //如果找到可行路径那么flag标记为1
                if(maze[i][j] == 0){
                    flag = 1;
                }
            }
            if(flag == 1){
//如果找到出口那么进栈
                Stack[top].d = d;  //进栈前记录当前立脚点的寻路方向
                top++;
                Node n1 = new Node();
                Stack[top] = n1;
                Stack[top].i = i;
                Stack[top].j = j;
                Stack[top].d = -1;
//已走过路径标记为-1防止重复路过
                maze[i][j] = -1;
            }else{
//否则退一步，然后继续试探可行路径
                maze[Stack[top].i][Stack[top].j] = 0;  //释放路径 为了以后的试探让路
                top--;
            }
        }

    }
    class Node{
        int i;
        int j;
        int d;
    }
    public static void main(String[] args) {
        new Maze1();
    }
}
